//给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰
//好 k 次： 
//
// 
// 选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。 
// 
//
// 注意：你可以对 同一堆 石子多次执行此操作。 
//
// 返回执行 k 次操作后，剩下石子的 最小 总数。 
//
// floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。 
//
// 
//
// 示例 1： 
//
// 
//输入：piles = [5,4,9], k = 2
//输出：12
//解释：可能的执行情景如下：
//- 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。
//- 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。
//剩下石子的总数为 12 。
// 
//
// 示例 2： 
//
// 
//输入：piles = [4,3,6,7], k = 3
//输出：12
//解释：可能的执行情景如下：
//- 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。
//- 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。
//- 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。
//剩下石子的总数为 12 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= piles.length <= 105 
// 1 <= piles[i] <= 104 
// 1 <= k <= 105 
// 
// Related Topics 数组 堆（优先队列） 
// 👍 5 👎 0

  
package com.zwy.leetcode.editor.cn;

import com.zwy.leetcode.Array;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class RemoveStonesToMinimizeTheTotal{
    public static void main(String[] args) {
        Solution solution = new RemoveStonesToMinimizeTheTotal().new Solution();
        int []piles = {10000};
        int k = 10000;
        solution.minStoneSum(piles,k);
      }
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public int minStoneSum(int[] piles, int k) {
         int sum=0;
        int t=0;
        int index=0;
        int len=piles.length;
        int []p=new int[k];
        int max=Integer.MIN_VALUE;
        Queue<Integer>queue=new LinkedList<>();
        for (int i = 0; i < piles.length; i++) {
            sum+=piles[i];
        }
        Arrays.sort(piles);
        p[0]=Integer.MIN_VALUE;

        for (int i = 0; i < k; i++) {
            if(len-index-1>=0) {
                if (piles[len - index - 1] > max) {
                    t = (int) Math.floor(piles[len - index - 1] * 1.0 / 2.0);
                    if (t == 0) return sum;
                    p[index] = piles[len - index - 1] - t;
                    piles[len-index-1]-=t;
                    index++;
                } else {
                    t = (int) Math.floor(max * 1.0 / 2.0);
                    p[index - 1] -= t;
                }
            }
            else{
                if(piles[0]>max){
                    t = (int) Math.floor(piles[0] * 1.0 / 2.0);
                    if (t == 0) return sum;
                    piles[0] = piles[0] - t;

                }
                else {
                    t = (int) Math.floor(max * 1.0 / 2.0);
                    p[index - 1] -= t;
                }
            }
            if(t!=0)
            Arrays.sort(p);
            max = p[p.length-1];
            sum -= t;
        }
        return sum;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}